package Chapter3;

public class KMP {
    public static int indexOf(String target, String pattern) {
        return indexOf(target, pattern, 0);
    }

    public static int indexOf(String target, String pattern, int begin) {
        int n = target.length(), m = pattern.length();
        if (begin < 0)
            begin = 0;
        if (n == 0 || n < m || begin >= n)
            return -1;
        int[] next = getNext(pattern);
        int i = begin, j = 0;
        while (i < n && j < m) {
            if (j == -1 || target.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
                if (n - i + 1 < m - j + 1)
                    break;
            }
        }
        return j == m ? i - m : -1;
    }

    public static int[] getNext(String pattern) {
        int j = 0, k = -1, next[] = new int[pattern.length()];
        next[0] = -1;
        while (j < pattern.length() - 1) {
            if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                j++;
                k++;
                next[j] = k;
            } else
                k = next[k];
        }
        return next;
    }

    public static int[] getNextval(String pattern){
        int j=0,k=-1,next[]=new int[pattern.length()];
        next[0]=-1;
        while (j<pattern.length()-1){
            if (k==-1||pattern.charAt(j)==pattern.charAt(k)){
                j++;
                k++;
                if (pattern.charAt(j)==pattern.charAt(k))
                    next[j]=next[k];
                else
                   next[j]=k;
            }else
                k=next[k];
        }
        return next;
    }


}
